| 翻訳と辞書 |
| Charging argument ： ウィキペディア英語版 |
Charging argument
In computer science, a charging argument is used to compare the output of an optimization algorithm to an optimal solution. It is typically used to show that an algorithm produces optimal results by proving the existence of a particular injective function. For profit maximization problems, the function can be any one-to-one mapping from elements of an optimal solution to elements of the algorithm's output. For cost minimization problems, the function can be any one-to-one mapping from elements of the algorithm's output to elements of an optimal solution.
==Correctness==
In order for an algorithm to optimally solve a profit maximization problem, the algorithm must produce an output that has as much profit as the optimal solution for every possible input. Let ''|A(I)|'' denote the profit of the algorithm's output given an input ''I'', and let ''|OPT(I)|'' denote the profit of an optimal solution for ''I''. If an injective function ''h : OPT(I) → A(I)'' exists, it follows that ''|OPT(I)| ≤ |A(I)|''. Since the optimal solution has the greatest profit attainable, this means that the output given by the algorithm is just as profitable as the optimal solution, and so the algorithm is optimal.
The correctness of the charging argument for a cost minimization problem is symmetric. If ''|A(I)|'' and ''|OPT(I)|'' denote the cost of the algorithm's output and optimal solution respectively, then the existence of an injective function ''h : A(I) → OPT(I)'' would mean that ''|A(I)| ≤ |OPT(I)|''. Since the optimal solution has the lowest cost, and the cost of the algorithm is the same as the cost of the optimal solution of the minimization problem, then the algorithm also optimally solves the problem.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Charging argument」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|